Most methods for handling an obstacle avoidance problem include a grid and/or graph based search, and relative velocity and distance based conditions or constraints.
In the grid and/or graph based search methods, grid cells or graph nodes are assigned obstacle dependent cost, thus allowing the algorithm to find collision free trajectories. However, the algorithms can require significant computer memory and the efficiency of the algorithms is heavily dependent on the heuristics used.
Further, these existing methods for generating physically realizable trajectories for an object that avoid collision with obstacles uses a network of safe-sets. The safe-sets are collections of trajectories for the object in closed-loop with a pre-designed controller that drives the object to a safe equilibrium point. The equilibrium points are selected by gridding the obstacle-free space. A safe and physically realizable trajectory can be found by searching the network for a sequence of equilibrium states that takes the object from the initial state to the target state. Wherein these pre-designed controllers can then be used to drive the state of the object to the corresponding equilibrium points in sequence while avoiding obstacles.
However, these pre-designed controllers that drive the object to the corresponding equilibrium state are pre-designed without information about the placement of obstacles relative to the equilibrium point. There are several disadvantages using the pre-designed controllers, for example, the maximum volume of the safe-sets is limited since the controllers are pre-designed, therefore the safe-set shapes are fixed. This can be a problem when the object must past through a narrow passage or close to an obstacle.
The equilibrium point around which the safe-sets are constructed are selected by gridding or graphing the obstacle-free space, is also a problem. For example, the aspect of gridding or graphing places the equilibrium points regularly, while the obstacles may not be uniformly distributed. Because of using the methods of gridding or graphing, results in the safe-sets near obstacles that must be small to avoid collisions. Thus, the gridding or graphing must be very fine producing an excessive number of points. However far from the obstacles, the larger safe-sets will cover many of their neighbors making them those sample points unnecessary. Finally, by only choosing equilibrium points that lie on a grid or graph, the prior art will miss nearby points that may be advantageous to have in the network.